package br.ufrj.dcc.org2.signature;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Set;

public class HashTable {
	private DataItem[] hashArray, hashArrayAux; // array de data items
	private int arraySize;
	private ArrayList<Separator> separatorArray;
	private int separatorSize;
	private BloomFilter bf;
	private int bloomSize;
	public HashTable(int size, int separatorSizeInBits, int bloomSize) // construtor
	{
		System.out.println("--"+separatorSizeInBits);
		arraySize = size;
		hashArray = new DataItem[arraySize];
		for (DataItem di : hashArray)
			di = new DataItem(-1);
		hashArrayAux = new DataItem[arraySize];
		for (DataItem di : hashArrayAux)
			di = new DataItem(-1);
		separatorSize = separatorSizeInBits;
		int separatorExpandedSize = (int) Math.pow(2, separatorSizeInBits);
		separatorArray = new ArrayList<Separator>(separatorExpandedSize);
		for (int i = 0; i < separatorExpandedSize; i++) {
			separatorArray.add(i, new Separator(separatorExpandedSize-1, separatorSize));
		}
		bf = new BloomFilter(bloomSize);
	}
	
	public int getHashSize() {
		return arraySize;
	}
	public ArrayList<Separator> getSeparator() {
		return separatorArray;
	}
	
	public DataItem[] getHashTable() {
		return hashArray;
	}
	
	public int hashFunc(int key) {
		return key % 11; // funcao de hash 
	}

	public int hashFuncInc(int key) {
		return (key/11) % 11; // funcao de hash que determina a proxima celula se a anterior estiver ocupada 
	}

	public void insert(DataItem item) { // insere um item
		int key = item.getKey(); // extrai chave
		int hashVal = hashFunc(key); // hasheia a chave
		//hashArray[hashVal] = item;
		
		ArrayList<Integer> probeChainArray = probeChain(key, hashVal);
		signatureInsetion(key, hashVal, probeChainArray);
	}
	
	private void signatureInsetion(int key, int hashVal, ArrayList<Integer> probeChainArray) {		
		boolean inserted = false;
		System.out.println("inserindo " + key +"...");
		for (Integer probe : probeChainArray) {
			if (probe.intValue() < separatorArray.get(hashVal).getKey()) {
				if (hashArray[hashVal] == null) {
					hashArray[hashVal] = new DataItem(key);
					System.out.println("Posicao " + hashVal + " vazia, inserindo...");
					inserted = true;
				} else {
					System.out.println("Posicao " + hashVal + "cheia,");
					int tempKey = hashArray[hashVal].getKey();
					int tempHashVal = hashFunc(tempKey);
					int tempProbe = (tempHashVal + 1)*tempKey % ((2^separatorSize)-1);
					if (tempProbe < probe.intValue()) {
						System.out.println("Probe existente em " + hashVal + " eh menor: " + tempProbe + ". Continuando.");
						separatorArray.get(hashVal).setKey(probe.intValue());
						hashVal += hashFuncInc(key);
					} else {
						System.out.println("Probe existente em " + hashVal + " eh maior: " + tempProbe + ". Trocando.");
						separatorArray.get(hashVal).setKey(tempProbe);
						hashArray[hashVal].setKey(key);
						signatureInsetion(key, hashVal, probeChainArray);
					}
				}
			}// else { // se for maior
				//System.out.println("Vai para o filtro de Bloom: " + key + ". Continuando.");
			//	bloomInsert(key);
		//		inserted = true;
		//	}			
		}
		if (inserted == false) {
			System.out.println("Vai para o filtro de Bloom: " + key + ". Continuando.");
			bloomInsert(key);
		}
	}

	private void bloomInsert(int key) {
		bf.setKey(key % 16);
		bf.setKey((key % 14) +2);
		bf.setKey((key % 13) +7);
		insertAux(key);
	}

	private void insertAux(int key) {
		int hashVal = key % 11;
		boolean control = true;
		if (hashArrayAux[hashVal] == null)
			hashArrayAux[hashVal] = new DataItem(key);
		else {
			while(control) {
				hashVal += (key / 11) % 11;
				hashVal %= arraySize;
				if (hashArrayAux[hashVal] == null) {
					hashArrayAux[hashVal] = new DataItem(key);
					control = false;
				}
			}
		}		
	}

	public ArrayList<Integer> probeChain(int key, int hashVal) {
		int nextProbe, originalHash;
		
		ArrayList<Integer> tempArray = new ArrayList<Integer>(); 
		
		nextProbe = ((hashVal + 1)*key )% ((2^separatorSize)-1);
		tempArray.add(nextProbe);
		originalHash = nextProbe;
		nextProbe = -1;
		boolean control = true;
		while (control) {			
			nextProbe = (hashVal + 1)*key % ((2^separatorSize)-1);
			if (nextProbe == originalHash)
				control = false;
			else {
				hashVal = nextProbe;
				tempArray.add(hashVal);
			}
		}	
		return tempArray;
	}

	public int find(int aKey) {
		int hashVal = hashFunc(aKey);
		ArrayList<Integer> probeChainArray = probeChain(aKey, hashVal);
		return signatureFind(aKey, hashVal, probeChainArray);
	}
	
	private int signatureFind(int key, int hashVal, ArrayList<Integer> probeChainArray) {		
		boolean inserted = false;
		System.out.println("Buscando " + key +"...");
		for (Integer probe : probeChainArray) {
			if (probe.intValue() < separatorArray.get(hashVal).getKey()) {
				if (hashArray[hashVal] == null) {
					return -1;
				} else {
					System.out.println("Posicao " + hashVal + "cheia,");
					int tempKey = hashArray[hashVal].getKey();
					int tempHashVal = hashFunc(tempKey);
					int tempProbe = (tempHashVal + 1)*tempKey % ((2^separatorSize)-1);
					if (tempProbe < probe.intValue()) {
						System.out.println("Probe existente em " + hashVal + " eh menor: " + tempProbe + ". Continuando.");
						hashVal += hashFuncInc(key);
					} else {
						return key;
					}
				}
			}			
		}
		if (inserted == false) {
			System.out.println("Vai para o filtro de Bloom: " + key + ". Continuando.");
			if (bloomFind(key))
				return key;
			return -1;
		}
		return -1;
	}
	private boolean bloomFind(int key) {
		if (bf.getKey(key % 16) && bf.getKey((key % 14) +2) && bf.getKey((key % 13) +7))
			return true;
		return false;
	}
}